package main.Q1801_1900;

import java.util.Arrays;
import java.util.Comparator;

public class Q1811_1820 {
    public static void main(String[] args) {
        System.out.println("Question1811：");
        System.out.println("Question1812：");
        System.out.println("Question1813：");
        System.out.println("Question1814：");
        System.out.println("Question1815：");
        System.out.println("Question1816：");
        System.out.println("Question1817：查找用户活跃分钟数");
        int[][] logs = new int[][]{{0, 5}, {1, 2}, {0, 2}, {0, 5}, {1, 3}};
        System.out.println(new Question1817().findingUsersActiveMinutes(logs, 5));
        System.out.println("Question1818：绝对差值和");
        System.out.println("Question1819：");
        System.out.println("Question1820：");
    }
}

class Question1817 {
    public int[] findingUsersActiveMinutes(int[][] logs, int k) {
        int[] result = new int[k];
        Arrays.sort(logs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];
            }
        });
        int lastId = logs[0][0], lastTime = logs[0][1], times = 1;
        for (int i = 1; i < logs.length; i++) {
            int curId = logs[i][0], curTime = logs[i][1];
            if (lastId == curId) {//同一用户
                if (lastTime != curTime) {//不同时间点
                    times++;
                }
                lastTime = curTime;
            } else {//不同用户
                result[times - 1]++;
                lastId = curId;
                lastTime = curTime;
                times = 1;
            }
        }
        //最后一个用户
        result[times - 1]++;
        return result;
    }
}

class Question1818 {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        final int MOD = 1000000007;
        int n = nums1.length;
        int[] rec = new int[n];
        System.arraycopy(nums1, 0, rec, 0, n);
        Arrays.sort(rec);
        int sum = 0, maxn = 0;
        for (int i = 0; i < n; i++) {
            int diff = Math.abs(nums1[i] - nums2[i]);
            sum = (sum + diff) % MOD;
            int j = binarySearch(rec, nums2[i]);
            if (j < n) maxn = Math.max(maxn, diff - (rec[j] - nums2[i]));
            if (j > 0) maxn = Math.max(maxn, diff - (nums2[i] - rec[j - 1]));
        }
        return (sum - maxn + MOD) % MOD;
    }

    public int binarySearch(int[] rec, int target) {
        int low = 0, high = rec.length - 1;
        if (rec[high] < target) {
            return high + 1;
        }
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (rec[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}